/**
 * MOTOR 2 - RAPID FLASH DYNAMICS
 * Copyright (c) 2007-2008, Michael Baczynski
 * Based on the Box2D Engine by Erin Catto, http://www.box2d.org
 * 
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 * 
 * * Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * * Neither the name of the polygonal nor the names of its contributors may be
 *   used to endorse or promote products derived from this software without specific
 *   prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package de.polygonal.motor2.math
{
	import de.polygonal.motor2.math.V2;
	import de.polygonal.ds.BinaryTreeNode;
	
	/**
	 * a bsp tree-based acceleration structure for performing
	 * extremal queries on a convex polygon, as described by
	 * Eberly, David in Game Physics, Morgan Kaufmann Publishers, 2004
	 * 
	 * the bsp tree is created for the polar dual supporting a
	 * O(log*n) search. note: i also tried the bisection method &
	 * the dobkin-kirkpatrick hierarchy, but eberly's method
	 * outperforms all other solutions.
	 */
	public class ConvexBSP
	{	
		//1: clockwise[default], -1 counterclockwise
		public static var VERTEX_ORDER:Number = 1;
		
		public static function createBSP(vertexCount:int, normals:Array, edges:Array):ConvexBSPNode
		{
			var NIR:Array, NIL:Array, AIR:Array, AIL:Array;
			var E:V2, N:V2;
			var ex:Number, ey:Number;
			var i:int, d0:Number, d1:Number;
			var R:ConvexBSPNode, L:ConvexBSPNode;
			
			NIR = []; NIL = [];
			AIR = []; AIL = [];
			
			E = edges[0]; 
			ex = E.x * VERTEX_ORDER;
			ey = E.y * VERTEX_ORDER;
			
			d0 = 0;
			for (i = 1; i < vertexCount; i++)
			{
				//perp(N) * D
				N = normals[i];
				
				d1 = ex * N.x + ey * N.y;
				
				if (d1 >= 0)
					NIR[NIR.length] = i;
				else
					NIL[NIL.length] = i;
				
				if (d0 >= 0 && d1 >= 0)
					AIR[AIR.length] = [i - 1, i];
				else
				if (d0 <= 0 && d1 <= 0)
					AIL[AIL.length] = [i - 1, i];
				else
				{
					AIR[AIR.length] = [i - 1, i];
					AIL[AIL.length] = [i - 1, i];
				}
				d0 = d1;
			}
			AIL[AIL.length] = [vertexCount - 1, 0];
			
			R = createInternalNode(vertexCount, normals, edges, NIR, AIR);
			L = createInternalNode(vertexCount, normals, edges, NIL, AIL);
			
			return createNode(0, R, L);
		}
		
		public static function createInternalNode(vertexCount:int, normals:Array, edges:Array, NI:Array, AI:Array):ConvexBSPNode
		{
			var LChild:ConvexBSPNode, RChild:ConvexBSPNode;
			var NIR:Array, NIL:Array, AIR:Array, AIL:Array, d:Array;
			var E:V2, N:V2;
			var ex:Number, ey:Number;
			var i:int, k:int, ni:int, t:Number, mid:int;
			
			NIR = [], NIL = [];
			AIR = [], AIL = [];
			
			k = NI.length;
			d = new Array();
			mid = int((NI[0] + NI[int(k - 1)]) / 2);
			
			E = edges[mid];
			ex = E.x * VERTEX_ORDER;
			ey = E.y * VERTEX_ORDER;
			
			ni = (NI[0] - 1); if (ni < 0) ni = k - 1;
			N = normals[ni];
			d[0] = ex * N.x + ey * N.y;
			for (i = 0; i < k; i++)
			{			
				ni = NI[i];
				
				if (ni == mid)
					d[int(i + 1)] = 1;
				else
				{
					N = normals[ni];
					
					t = d[int(i + 1)] = ex * N.x + ey * N.y;
					t >= 0 ? NIR[NIR.length] = ni : NIL[NIL.length] = ni;
				}
			}
			
			ni = NI[int(k - 1)] + 1;
			if (ni == vertexCount) ni = 0;
			N = normals[ni];
			d[d.length] = ex * N.x + ey * N.y;
			
			k = AI.length;
			for (i = 0; i < k; i++)
			{				
				if (d[i] >= 0 && d[int(i + 1)] >= 0)
					AIR[AIR.length] = AI[i];
				else 
					AIL[AIL.length] = AI[i];
			}			
			
			RChild = null;
			if (NIR.length > 0)
				RChild = createInternalNode(vertexCount, normals, edges, NIR, AIR);
			else
			{
				if (AIR.length > 0)
					RChild = createNode(AIR[0][1]); //leaf node containing arc
//				else
//					RChild = createNode(0);
			}
			
			LChild = null;
			if (NIL.length > 0)
				LChild = createInternalNode(vertexCount, normals, edges, NIL, AIL);
			else
				LChild = createNode(AIL[0][1]); //leaf node containing arc
			
			var node:ConvexBSPNode = createNode(mid, RChild, LChild);
			return node;
		}
		
		public static function createNode(I:int, R:ConvexBSPNode = null, L:ConvexBSPNode = null):ConvexBSPNode
		{
			var n:ConvexBSPNode = new ConvexBSPNode();
			n.I = I;
			
			n.R = R;
			n.L = L;
			
			n.right = R;
			n.left  = L;
			
			return n;
		}
	}
}